Buffers include memory that provides temporary data storage. Buffers are often used to store data that is transferred between two locations or devices. For example, a buffer may temporarily store data that is transferred between two communications devices that operate at different speeds. The buffer may be implemented using Static Random Access Memory (SRAM), which has low latency and is generally expensive. The buffer may be a First In, First Out (FIFO) buffer, which outputs data in the same order that the data is stored. FIFO buffers are commonly incorporated in network devices such as switches and routers.
High-speed communication lines are sometimes formed using multiple channels that operate at variable lower speeds. For example, an Optical Carrier (OC) 192 line may carry 16 channels traffic. While the available total bandwidth is limited to OC192 rate, data traffic for each channel may change from zero to the whole OC192 rate.
Conventional FIFO buffers for multi-channel communications devices store data from each channel in a dedicated block of memory, or can be viewed as using memory block linearly or incrementally. For example, a 16-channel communications device with 20 KB of memory for each channel requires a total of 320 KB of memory. This approach is reliable when the dedicated blocks of memory are of a sufficient size to meet the bandwidth requirements of the corresponding channel. As the number of channels increases, the total required memory also increases. For example, a similar device with 256 channels requires a total of 5,120 KB of memory. The cost of the dedicated low latency memory for applications with a large number of channels is prohibitive. Since total throughput is still limited to OC192 rate, the system typically uses only a very small fraction of the overall memory at any given moment.
In an exemplary conventional FIFO buffer, 16 channels can be combined to form an OC192 line. Each FIFO has 20 Kbytes and the system has a total of 320 Kbytes. The memory is divided into 1 Kbyte blocks, which are numbered from 0 to 319. A first FIFO uses memory blocks 0 to 19, a second FIFO uses blocks 20 to 39, etc. Each FIFO uses its memory blocks linearly (incrementally) and in a known sequence. The known sequences that are used by the different FIFOs do not overlap.
In another approach, the memory is divided into smaller blocks having a fixed size. When a FIFO buffer requires memory for a channel, the FIFO buffer requests a block from a block manager, which monitors the use of memory blocks. Since memory is dynamically assigned to each channel, a FIFO buffer can store data for an increased number of channels. In other words, the ratio of total buffer memory size to the number of channels is reduced as compared to the dedicated memory approach. Since the memory blocks are assigned to a channel when needed, the data from a particular channel is not necessarily stored in sequential memory locations. Therefore, during read back, the FIFO buffer uses a block index table to determine the next memory block. This approach requires additional logic and hardware, which increases the cost of the buffer.